public class LeetCode236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //判断是否为空
        if (root == null || root == p && root == q) {
            return root;
        }
        //递归地在左右树中寻找p 和 q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左右子树都找到了非空的结果，说明p和q分别位于当前节点的两侧
        // 因此当前节点就是它们的最近公共祖先
        if (left != null && right != null) {
            return root;
        }
        // 如果只有一侧找到了非空的结果，那么就返回这一侧的结果
        // 如果两侧都是空，则返回空
        return left != null ? left : right;
    }
}
